<?php
/**
 * Created by PhpStorm.
 * User: simaguo
 * Date: 2018/6/11
 * Time: 22:53
 */

namespace Simaguo\DS\Lists;

class StaticLinkedList
{
    protected $list;
    protected $size;
    protected $max;

    public function data()
    {
        return $this->list;
    }

    public function __construct($size)
    {
        $this->size = $size;
        $this->max = $size + 1;
        for ($i = 1; $i <= $size; $i++) {
            $this->list[$i] = $this->node(null, $i + 1);
        }
        $this->list[0] = $this->node(0, 1);//存放第一个空闲位
        $this->list[$this->max] = $this->node(null, 0);//存放第一个有数据的位置
    }

    protected function node($elem, $cursor)
    {
        return array(
            'cursor' => $cursor,//下一个数据的下标,但第一位游标保存第一个没数据的下标
            'elem' => $elem,//下一个数据的值,但第一位保存静态链表使用长度
        );
    }

    public function length()
    {
        return $this->list[0]['elem'];//保存链表已使用长度
    }

    protected function freeSubscript()
    {
        $i = $this->list[0]['cursor'];

        if ($this->list[0]['cursor']) {
            $this->list[0]['cursor'] = $this->list[$i]['cursor'];
        }

        return $i;
    }

    public function insert($index, $elem)
    {
        $length = $this->length();

        if ($index < 1 || $index > $length + 1) {
            return false;
        }

        if ($length + 1 > $this->size) {
            return false;
        }
        $subscript = $this->freeSubscript();//插入处下标

        $pre = $this->max;//第0处的下标

        for ($j = 1; $j < $index; $j++) {
            $pre = $this->list[$pre]['cursor'];//第index-1处的下标
        }

        $cursor = $this->list[$pre]['cursor'];

        $this->list[$subscript] = $this->node($elem, $cursor);
        $this->list[$pre]['cursor'] = $subscript;//指向新下标

        $this->list[0]['elem']++;

        return true;
    }

    public function add($elem)
    {
        return $this->insert($this->length() + 1, $elem);
    }

    public function get($index)
    {
        if ($index < 1 || $index > $this->length()) {
            return false;
        }
        $pre = $this->max;
        for ($i = 0; $i < $index; $i++) {
            $pre = $this->list[$pre]['cursor'];
        }

        return $this->list[$pre]['elem'];
    }

    public function delete($index)
    {
        if ($index < 1 || $index > $this->length()) {
            return false;
        }
        $pre = $this->max;

        for ($i = 1; $i < $index; $i++) {
            $pre = $this->list[$pre]['cursor'];//第index-1处的下标
        }
        $origin = $this->list[$pre]['cursor'];

        $this->list[$pre]['cursor'] = $this->list[$origin]['cursor'];

        $elem = $this->list[$origin]['elem'];
        $this->list[$origin]['elem'] = null;
        $this->list[$origin]['cursor'] = $this->list[0]['cursor'];


        $this->list[0]['cursor'] = $origin;
        $this->list[0]['elem']--;

        return $elem;
    }
}

